Focusing on the problem that open and insecure wireless channel between reader and tag in Radio Frequency IDentification (RFID) system is vulnerable to multiple malicious attacks, a new ultra-lightweight RFID Mutual Authentication Protocol based on Regeneration (RRMAP) was proposed. Firstly, the regeneration transformation of the first-stage reverse sequence self-combination transformation on two binary arrays was performed to achieve its own bit confusion effect. Secondly, the result of first-stage was used for the second-stage parity adjacent crossover-XOR operation, thus whole regeneration transformation was completed. Finally, through new definition of regeneration transformation, the left circular shift operation and modular 2^ m addition operation were combined to construct secret communication messages during authentication process, which could effectively solve security problems existing in RFID system currently. The BAN (Burrows-Abadi-Needham) logic formal proof was given to show the availability of protocol. The security analysis and performance comparison show that RRMAP has strong security and privacy protection attributes which can resist some common malicious attacks.